/**
 * 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
 *https://leetcode.cn/problems/unique-binary-search-trees/
 *
 */
class NumTrees {
    int[][] meno;//备忘录记录子问题的状态
    public int numTrees(int n) {
        meno=new int[n+1][n+1];
        return count(1,n);
    }
    public int count(int lo,int hi) {
        if(lo>=hi) {
            return 1;
        }
        if(meno[lo][hi]!=0) {//查看备忘录
            return meno[lo][hi];
        }
        int res=0;
        for(int i=lo;i<=hi;i++) {//以i为根节点，lo到i-1为左子树，i+1到hi为右子树
            int left=count(lo,i-1);
            int right=count(i+1,hi);
            res+=left*right;
        }
        meno[lo][hi]=res;
        return res;
    }
}